SDNs have gained significant momentum in the networking industry recently. SDNs can potentially simplify network operation and administration, facilitate innovation through software, and reduce the time to market for new network functions. One critical component of the SDN architecture is wildcard based flow matching. Openflow is a widely used SDN implementation. The SDN architecture relies on wildcard matching rules at all the switches in the data path. Software running in a central controller installs and updates such rules in the switch flow table, and hence controls how each packet is processed in the network.
Ternary content addressable memory (TCAM) is the hardware solution for wildcard matching in routers and switches. Despite its flexibility, TCAM is very expensive and has high power consumption.
To understand the context of the problem, the basic operation of the SDN network will be described using Openflow as an example. A typical Openflow network consists of multiple switches and a central controller. There are one or more flow tables on each switch that are capable of doing wildcard-based flow matching. Packet processing and forwarding are done at the switches based on the rules stored in the flow tables. The central controller connects to each switch and controls what rules are set up for each flow.
The basic life-cycle of a flow in the Openflow network may be described as follows. First, a host (for example, a physical host or virtual machine) generates a packet. Second, the first-hop switch (physical switch or virtual switch in hypervisor) looks up the packet in its flow table and tries to find a match by using wildcard matching. Third, because this is the first packet of the flow, no match is found, and hence the packet is forwarded to the central controller. The central controller processes the request, computes the forwarding or flow path for the packet, and installs rules at the corresponding switches along the path to be followed by the packet. The rules contain instructions on how the packet should be treated, e.g., to be queued, forwarded to a port, or dropped. Fourth, the first switch processes the packet according to the rule. Fifth, in a similar way, the other switches along the path of the packet conduct wildcard matching for the packet and process it accordingly. The process continues until the packet is delivered to the destination host. Finally, later packets that belong to the same flow can be processed in the switches without consulting the central controller, because the switches on the path already have the flow entry installed in the flow table.
The existing solution for flow matching uses either software or hardware. Software solutions can be used in hypervisor virtual switches, but are generally not suitable for physical switching devices in production networks due to their limited speed. The hardware solution relies on TCAM, which are very expensive and have high power consumption.